package com.shuzijun.leetcode.editor.cn;

import java.util.HashSet;

public class RouteBetweenNodesLcci{
    public static void main(String[] args) {
         
         Solution solution = new RouteBetweenNodesLcci().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private boolean[] visited;
        private HashSet<Integer>[] adj;
        private boolean found = false;
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        visited = new boolean[n];
        adj = new HashSet[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new HashSet<Integer>();
        }
        for (int i = 0; i < n; i++) {
            if (!adj[graph[i][0]].contains(graph[i][1])){
                adj[graph[i][0]].add(graph[i][1]);
            }
        }
        dfs(start,target);
        return found;

    }

        private void dfs(int cur, int target) {
            if (found)return;
            if (cur == target){
                found = true;
                return;
            }

            visited[cur] = true;

            for (Integer next:  adj[cur]) {
                if (!visited[next]){
                    dfs(next,target);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}